package 算法.leetcode.offer;

import java.util.Stack;

/**
 * @author lchenglong
 * @date 2022/4/27
 */
public class Offer33 {

    public static void main(String[] args) {
        Offer33 instance = new Offer33();
        boolean ans = instance.verifyPostorder(new int[]{1, 3, 2, 6, 5});
        System.out.println(ans);
    }

    /**
     * 单调栈
     *
     * 后续遍历倒序-->[根|右子树|左子树]
     *
     * 设后序遍历倒序列表为 [r_{n}, r_{n-1},...,r_1]，遍历此列表，设索引为 i ，若为 二叉搜索树 ，则有：
     * - 当节点值 r_i > r_{i+1}时： 节点 r_i 一定是节点 r_{i+1}的右子节点。
     * - 当节点值 r_i < r_{i+1}时： 节点 r_i一定是某节点 root 的左子节点，
     * 且 root 为节点 r_{i+1}, r_{i+2},..., r_{n}中值大于且最接近 r_i的节点(root 直接连接 左子节点 r_i)
     * 当遍历时遇到递减节点 r_i < r_{i+1} ，若为二叉搜索树，则对于后序遍历中节点 r_i
     * 右边的任意节点 r_x \in [r_{i-1}, r_{i-2}, ..., r_1]，必有节点值 r_x < root
     *
     * @param postorder
     * @return
     */
    public boolean verifyPostorder(int[] postorder) {
        // i*2,i*2+1 root i = 4,左子树:i*2= 4>>i=2,右子树:左子树+1
        Stack<Integer> stack = new Stack<>();
        int root = Integer.MAX_VALUE;
        for (int i=postorder.length-1;i>=0;i--){
            if (postorder[i]>root)return false;
            while (!stack.empty()&&stack.peek()>postorder[i])
                // 单调栈,大于当前值则出栈
                root = stack.pop();
            stack.push(postorder[i]);
        }
        return true;
    }
}
